The invention is in the field of information processing. Specifically, the invention relates to conversion from residue number system (RNS) representations of data to mixed base number system representations of data using a parallel residue to mixed base converter.
The RNS has received considerable attention in recent times as an effective tool for performing single step, parallel computation of sums, differences, and products. A system employing the RNS may be used for high speed, real time, parallel processing of data.
A difficulty associated with actually achieving fast computation with the RNS is that an RNS representation of a number does not provide explicit sign and magnitude information. This sign/magnitude problem could be solved by converting the number from RNS representation to fixed based representation using the implicit sign and magnitude information of the fixed based system. Unfortunately, this fixed base conversion process is very time consuming due to the need to multiply large fixed base numbers. An alternative is to convert the RNS representation into mixed base representation.
Residue Arithmetic and Its Application to Computer Technology. N. S. Szabo and R. I. Tanaka, (McGraw Hill, New York, 1967) and "Residue Arithmetic: A Tutorial with Examples," F. J. Taylor Computer Vol. 17 No. 5, pp. 50-62 (May 1984), both of which are hereby incorporated by reference, provide general background information on the RNS and the mixed base number system. Rapid conversion from RNS representation to mixed base representation is important for sign/magnitude comparison as well as for overflow detection and rescaling.
The Szabo and Tanaka text provides procedures for converting between RNS representations and mixed base representations. Unfortunately, these procedures require performance of a time consuming sequence of arithmetic operations. A slow conversion process decreases the efficiency of an associated information processing system and is thus undesirable.
U.S. Pat. Nos. 4,107,783 issued to Huang, 4,752,904 issued to Paul, 4,709,345 issued to Vu, 4,528,641 issued to Burrows, and 4,281,391 issued to Huang disclose residue to mixed base converters which use ROMs (read only memory) and latches, adders, or processors to implement the conversion process. The inventions disclosed in these patents perform the conversion process in a time consuming series of pipelined stages and require complex hardware, and are thus unsuitable for many applications due to the long period of time required for the pipelined conversion process and the complexity of the hardware required. Accordingly, there is a need for high speed RNS representation to mixed base representation converters.